#include <stdio.h>
#include <stdlib.h>

typedef struct String {
    char *data;
    int len;
} String;

String *initString()
{
    String *s = (String *)malloc(sizeof(String));
    s->data = NULL;
    s->len = 0;
    return s;
}
//重新赋值的函数
void StringAssign(String *s, char *data) 
{
    if (s->data) free(s->data); 
    int len = 0; //data len
    char *tmp = data;
    while (*tmp++ != '\0') {
      len++;
    }
    if (len == 0) {
        s->data = NULL;
        s->len = 0;
    } else {
        s->data = (char *)malloc(sizeof(char) * (len+1));
        tmp = data;
        s->len = len;
        int i;
        for (i = 0; i < len; i++) {
            s->data[i] = *tmp;
            tmp++;
        }
    }
}

int forceMatch(String *master, String *sub) 
{
    int i = 0; int j = 0;
    while (i < master->len && j < sub->len) {
        if (master->data[i] == sub->data[j]) {
        i++; j++;
        } else {
            j = 0; i = i - j +1; //下标从0开始
        }
    }
    if (j == sub->len) {
            printf("match sucess!\n");
            return i-j;//即 i-1->sub.len+1
    } else {
            printf("match fail!\n");
            return -1;
    }
}

int *getNext(String *s)
{
    int i = 0; 
    int j = -1;
    int *next = (int *)malloc(sizeof(int) *s->len);
    next[i] = j;
    while (i < s->len-1) {
        if (j == -1 || s->data[i] == s->data[j]) {
            ++j; 
            ++i;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

int *getNextval(String *s, int *next)
{
    int i = 0; 
    int j = -1;
    int *nextval = (int *)malloc(sizeof(int) *s->len);
    nextval[i] = j;
    while (i < s->len-1) {
        if (j == -1 || s->data[i] == s->data[j]) {
            ++j; 
            ++i; //重点
            if (s->data[i] == s->data[j]) {
                nextval[i] = nextval[j];
            } else {
                nextval[i] = j;
            }
        } else {
            j = nextval[j];
        }
    }
    return nextval;
}

//结合getNext() 和 getNextval();
int *getNextMax(String *s)
{
    int i = 0; 
    int j = -1;
    int *next = (int *)malloc(sizeof(int) *s->len);
    next[i] = j;
    while (i < s->len-1) {
        if (j == -1 || s->data[i] == s->data[j]) {
            ++j; 
            ++i;
            next[i] = j; //
            if (s->data[i] == s->data[j]) {// s->data[i] == s->data[next[i]] 这时的下标j表示上一个的前后缀的下一个
                next[i] = next[j];
            }
        } else {
            j = next[j];
        }
    }
    return next;
}

int kmpMatch(String *master, String *sub, int *next) 
{
    int i = 0; 
    int j = 0;
    while (i < master->len && j < sub->len) {
        if (j == -1 || master->data[i] == sub->data[j]) {
            ++i; ++j;
        } else {
            j = next[j];
        }
    }
    if (j == sub->len) {
        printf("match success!\n");
        return i-j;
    } else {
        printf("match fail!\n");
        return -1;
    }
}

void printString(String *s)
{
    for (int i = 0; i < s->len; i++) {
        printf(i == 0 ? "%c" : "->%c", s->data[i]);
    }
    printf("\n");
}
//调试用的
void printNext(int *next, String *s) 
{
    for (int i = 0; i < s->len; i++) {
        printf("%d ", next[i]);
    }    
    printf("\n");
}

int main(int argc, char *argv[]) 
{



    String *s = initString();
    StringAssign(s, "abab");
    printString(s);
    
    int *nextval = getNextMax(s);
    printNext(nextval, s);
    String *t = initString();
    StringAssign(t, "ll");
    printString(t);
    
    printf("%d\n", kmpMatch(s, t, getNextMax(t)));
    return 0;
}

 /*String *s = initString();
    StringAssign(s, "hello world");
    printString(s);
    printf("\n---\n");
    char *test = "\0";
    StringAssign(s, test);
    printString(s);

    printf("\n---\n");
    String *t = initString();
    StringAssign(t, "ll");
    printString(t);
    printf("pos: %d\n", forceMatch(s, t));
    */